class Solution(object):
    def printTree(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[str]]
        """
        depth = 0
        now = [root]
        while now:
            depth += 1
            next_stack = []
            for node in now:
                if node.left:
                    next_stack.append(node.left)
                if node.right:
                    next_stack.append(node.right)
            now = next_stack
        out = [['' for _ in range(2 ** depth - 1)] for _ in range(depth)]

        def search(node, left, right, depth):
            mid = (left + right) // 2
            out[depth][mid] = str(node.val)
            if node.left:
                search(node.left, left, mid - 1, depth + 1)
            if node.right:
                search(node.right, mid + 1, right, depth + 1)

        search(root, 0, 2 ** depth - 2, 0)
        return out